\subsection{Übungsblatt 5 - Diskreter Logarithmus}
\subsubsection{Übung 11.9.2}
Aufgabenstellung:
Verwenden Sie den Babyste-Giantstep-Algorithmus, um den diskreten Logarithmus von 15 zur Basis 2 mod 239 zu berechnen. \newline
$\alpha = 15$ \newline
$\gamma = 2$ \newline
$m = \left\lceil \sqrt{238}\right\rceil \approx 16$ (aufgerundet) \newline \newline
\textbf{Babystep-Menge:} \newline \newline
Berechnung: $\alpha*\gamma^{-r}$ \newline
1. Schritt: $15*2^{0} = 15$ \newline
2. Schritt: $15*2^{-1} -->$ inverse berechnen von $2^{-1}$ \newline
$y * 2 \equiv$ 1 mod $239$\newline
Das inverse ist 120. \newline
$15*120$ mod $239 = 127$ \newline
Die n\"achsten Schritte berechnet man, indem man das Ergebnis aus dem vorherigen Schnitt mit $2^{-1}$ multipliziert mod 239 $($also 120, da mit der inversen von $ 2^{-1}$ gerechnet wird$)$ \newline
3. Schritt: $127*120$ mod 239 = 15240 mod 239 = 183\newline
\newline
\textbf{B}=$[(15,0),(127,1),(183,2),\textbf{(211,3)},(225,4),(232,5),(116,6),(58,7),\newline (29,8),(134,9),(67,10),(153,11),(196,12),(98,13),(49,14),(144,15)]$ \newline \newline
\textbf{Giantstep-Menge:} \newline \newline
Berechnung: $\gamma^{qm}$\newline
1. Schritt: $2^{16*1}$ mod $239 = 50$ \newline
Die n\"achsten Schritte k\"onnen, analog zum Babystep, \"uber die Multiplikation des Ergebnisses aus dem vorhergegangenen Schritt mit $2^{16}$ mod 239 (also 50 mod 239) berechnet werden. \newline
2. Schritt: $2^{16*2}$ mod $239 = 2^{16}$ * $2^{16}$ mod 239 = $50*50$ mod $239 = 110$ \newline
\newline
\textbf{G}=$[(50,1),(110,2),(3,3),(150,4),(91,5),(9,6),\textbf{(211,7)}]$ \newline
\newline
Da wir jetzt unsere gesuchten Zahlen gefunden haben k\"onnen wir das x ausrechnen: \newline
Hierf\"ur ben\"otigen wir die Schritte, bei denen der Giantstep und der Babystep das gleiche Ergebnis haben und die Variable m.\newline
$x = q*m+r$ \newline
$x = 7 * 16 + 3  $ \newline
$x= 115$ \newline
Hiermit haben wir den diskreten Logarithmus gel\"ost.\newline

\subsubsection{Übung 11.9.4}

Berechne den diskreten Logarithmus $3^x \equiv 2 \mbox{ mod } 65537$ mit dem  
Pohlig-Hellman-Algorithmus.\\
Die Gruppenordnung ist $n = 65536 = 2^{16}$ \\
Wir berechnen $x$:
$$
\begin{array}{lll}
  n_2 = n/p^{e(2)} = 1, & \gamma_2 = \gamma^{n_2} = \gamma^1 = 3, &\alpha_p = \alpha^{n_2} = \alpha^1 = 2
\end{array}
$$
Wir Reduzieren das Problem auf eine Untergruppe mit der Primzahlpotanzordnung. Was hier eigentlich keinen Unterschied macht.
Die Ordnung und damit auch die Aufgabe bleiben dieselben, weil die Ordnung nur eine Primzahlpotenz ($s^{16}$) hat.
$$\gamma_2^{x} \equiv \alpha_2 \mbox{ mod } 65537$$
$$3^{x} \equiv 2 \mbox{ mod } 65537$$

Wir reduzieren das Problem auf die eine Untergruppe mit der Ordnung 2. Dazu verwenden wir die p-adische Darstellung von x:
$$x = x_0 + x_1*2 + \ldots + x_{15} * 2^{15}$$

Nun berechnen wir alle $x_i$ für $0 \leq i \leq 15$:
$(\gamma^{p^{e-1}})^{x_i} \equiv \alpha_i^{p^{e-i-1}}$
dabei sind:\\
$\gamma = 3$, $p=2$, $e=16$ und $\alpha_i = \alpha\gamma^{-(x_0+x_1p+\ldots+x_{i-1}p^{i-1})}$

Wir berechnen $x_0$:
$$3^{2^{15}x_0} \equiv 2^{2^{15}} \mbox{ mod } 65537$$
$$65536^{x_0} \equiv 1  \mbox{ mod } 65537$$
also ist $x_0 = 0$.
Solange die Koeffizienten weiterhin 0 sind bleibt $\alpha_i = 2$.\\
Es ist:
$$2^{2^{14}} \equiv 2^{2^{13}} \equiv \ldots \equiv 2^{2{^5}} \equiv 1 \mbox{ mod } 65537$$
Deshalb sind die Koeffizienten $x_1$ bis $x_{10} = 0$\\
Wir berechnen den Koeffizienten $x_{11}$ dabei ist $\alpha_{11} = 2$:
$$65536^{x_{11}} \equiv 2^{2^{4}} \mbox{ mod } 65537$$
$$65536^{x_{11}} \equiv 65536 \mbox{ mod } 65537$$
Damit ist $x_{11} = 1$ und $\alpha_{12} = 2*3^{-2048} \mbox{ mod } 65537 \equiv 16384$
$$x_{12}: 65536^{x_{12}} \equiv 16384^{2^3}  \mbox{ mod } 65537$$
$$65536^{x_{12}} \equiv 65536 \mbox{ mod } 65537$$
Also ist $x_{12} = 1$ und $\alpha_{13} = 2*3^{-(2^{11}+2^{12})} = 256$
$$x_{13}: 65536^{x_{13}} \equiv 256^{2^2}  \mbox{ mod } 65537$$
$$65536^{x_{13}} \equiv 1 \mbox{ mod } 65537$$
Also ist $x_{13} = 0$ und $\alpha_{14} = a_{13} = 256$
$$x_{14}: 65536^{x_{14}} \equiv 256^{2^1}  \mbox{ mod } 65537$$
$$65536^{x_{14}} \equiv 1 \mbox{ mod } 65537$$
Also ist $x_{14} = 1$ und $\alpha_{15} = 2*3^{-(2^{11}+2^{12}+2^{14})} = 65536$
$$x_{15}: 65536^{x_{15}} \equiv 65536^{2^0}  \mbox{ mod } 65537$$
Also ist $x_{15} = 1$\\
Um $x$ zu berechnen verwende ich wegen der Übersichtlichkeit die Binärdarstellung:
$$x = 1101100000000000_2 = 55296_{10}$$
Damit ist $x \equiv 55296 \mbox{ mod } 65536$ und $x = 55296$